package com.atguigu.dq;

public class P53 {
    public static void main(String[] args) {
        //期望输出：6
        int[] arr =  {5, 4, -1, 7, 8};//{1};//{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(arr));
    }

    private static int maxSubArray(int[] arr) {
        return maxSubArray(arr,0,arr.length-1);
    }

    private static int maxSubArray(int[] arr, int start, int end) {

        if(start>=end){
            return arr[start];
        }

        //mid是我分割的位置
        int mid = (start+end)/2;
        //因此这个数组的答案①要么在左子数组上，②要么在右子数组上，③要么横跨
        int leftMax = maxSubArray(arr,start,mid);
        int rightMax = maxSubArray(arr,mid+1,end);
        int crossMax = getCrossMax(arr,start , mid , end) ;
        return Math.max(crossMax,Math.max(leftMax,rightMax)) ;
    }

    private static int getCrossMax(int[] arr, int start, int mid, int end) {
        //分别算左边最大值和右边最大值，然后两者相加，就是答案
        int leftMax = arr[mid];
        int leftSum = arr[mid];
        for(int i = mid-1;i>=start;i--){
            leftSum = leftSum+arr[i];
            leftMax = Math.max(leftSum,leftMax);
        }

        int rightMax = arr[mid+1];
        int rightSum = arr[mid+1];
        for(int i = mid+2;i<=end;i++){
            rightSum = rightSum+arr[i];
            rightMax = Math.max(rightSum,rightMax);
        }

        return leftMax+rightMax;
    }


}
